# 串联所有单词的子串： https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/submissions/
"""
    这题有些难
"""

class Solution:
    def findSubstring(self, s: str, words: list) -> list:
        """
            滑动窗口解题， 利用hash进行比较。 
            hash比较当前窗口内该单词数量 是否和 words中该单词数量相同。 且 wordsNum，记录 words单词数，当这些单词数都匹配，那就说明整个 匹配。
            监测到字符 matchWordNum就加1，不符合的话， 在循环里就会被减到，说的简单，但是不是很容易想到和理解~
        """
        rst = []
        # 1. 先构成 words 的 map， 再与窗口内元素构成的map 进行比较，看是否相同
        wordsMap = dict()
        wordsNum = len(words)
        wordLen = len(words[0])
        for word in words: wordsMap[word] = wordsMap.get(word, 0) + 1
        # 重点： for 循环， 字符长度的 每个都可以当做字符的开始
        for m in range(wordLen):
            i = j = m
            n = len(s)
            windowsMap = dict()
            matchWordNum = 0
            # 2. 滑动窗口
            while j <= n - wordLen:
                # 3. 先确定出一个单词, 并添加进 窗口字典中，默认 匹配
                word = s[j: j + wordLen]
                
                windowsMap[word] = windowsMap.get(word, 0) + 1
                # if windowsMap.get(word, 0) == wordsMap.get(word, 0):
                matchWordNum += 1   
                # print("word", word, matchWordNum) 
                # 4. 这里判断当前的 word 是否再 words中，如果不在就要 右移i， 将单词移除。 因为前面可能有多个单词了，需要使用 while循环
                while windowsMap.get(word, 0) > wordsMap.get(word, 0):
                    # 取i对应的单词
                    iWord = s[i: i + wordLen]
                    
                    windowsMap[iWord] -= 1
                    i += wordLen
                    # 如果当前减掉的是 words里的单词，且数量小于 words里的，才减去
                    # if iWord in wordsMap and windowsMap.get(word, 0) < wordsMap.get(word, 0):
                    matchWordNum -= 1
                # print(j, windowsMap)
                # 5. 如果匹配的数量相等了，那就找到了
                if wordsNum == matchWordNum: 
                    rst.append(i)

                # 6.  j 前移
                j += wordLen

        return rst

